A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
This specification contains a microfiche appendix in two parts A and B. The microfiche appendix consists of one (1) microfiche having 47 frames.
1. Field of the Invention
The invention relates to determining the most active traffic flow rates among many on a communications network and, in particular, to using an integrated circuit configured to create a table indicating flow rates for particular packet address identifications.
2. Related Art
FIG. 1 shows a block diagram of a switch 10 in a typical network 12. As shown, a plurality of sources 14A and 14B, destinations 16A and 16B, and source/destination combinations 18A and 18B are connected to switch 10. Switch 10 may receive a signal from source 14A on line 20 which represents information contained in a typical packet form using a conventional Media Access Control (MAC) addressing protocol. Switch 10 receives the signal, examines the destination address identification in the packet, and directs the packet be sent using a second signal on, for example, line 22 to the correct destination such as destination 16B.
It is of interest to monitor the traffic activity through a network device, such as switch 10, so that the most active packet addresses are identified. Packet activity may be of interest for many network related reasons, including administration and maintenance requirements such as reconfiguration. Thus selected source addresses, destination addresses, and source/destination pair addresses may be of particular interest. Traffic activity is presently monitored using a remote device such as an RMON (Remote Monitor) Probe. This device is separate from switch 10.
What is desired is an apparatus and method of identifying the packet identifications most frequently handled by a switch or other network device that is integral to the device itself. It is furthermore desirable that the apparatus be embodied in a single integrated circuit.
In an embodiment of the invention, an integrated circuit is configured to act as a monitor that uses a modified xe2x80x9cleaky bucketxe2x80x9d model to distinguish the most active packet identifications handled by a network device such as a switch. In one embodiment the monitor creates a traffic activity table in random access memory (RAM) that contains the identification and an associated traffic activity value for each of the most active packet address identifications. The table contains a fixed number of available records, and each record has a field for a unique packet identification and a field for an associated activity value (a xe2x80x9cbucketxe2x80x9d associated with each identification).
The monitor periodically samples identifications of packets received by a switch. The sampled packet identification is stored in a buffer and is sequentially compared against each record in the traffic activity table. For each sampled packet identification, all activity table records are examined once. If the sampled identification matches an identification in the activity table, the associated activity value is increased (the bucket begins to fill). If the sampled identification does not match an identification in the current table record, the table record identification""s associated activity value is decreased (the bucket leaks). Over time, if an activity value decreases to zero, the record is considered empty. If the sampled identification does not match any identification in the table, and if an empty record exists in the table, the sampled identification is placed in an empty record in the table and an initial value is assigned to its associated activity value.
The rate at which the activity values are increased and decreased is significant. For each comparison in which the sampled identification does not match a current table record identification, the matching activity value is decreased by a fixed amount (the bucket leaks at a fixed rate). But if a sampled identification matches a current table record identification, the matching activity value is increased by an amount inversely proportional to the activity value (the bucket is filled at a rate inversely proportional to the current bucket contents). The relationship between the inversely variable increase amount and the constant decrease amount yields an activity value upper limit that indicates how often a particular packet identification is being sampled (the inversely proportional fill rate and the constant leak rate signifies that for a particular number of times a particular packet identification is sampled, the bucket can only fill to a specified level). Conversely, a particular packet sample rate may be indicated by choosing a specified increase amount and upper limit corresponding to the particular packet sample rate (a particular packet""s activity reaches a particular minimum when the bucket fills to a certain level).
The monitor increases the activity values using addends stored in a look up table. The addend table contains discrete activity value upper limits and a unique addend for each upper limit. Thus, if a sampled identification matches an existing identification in the activity table, the monitor examines the activity table""s associated activity value, looks to the addend table to find the range in which the activity value falls, and determines the appropriate addend. The monitor then adds the addend to the current activity value and updates the current activity table record with the new activity value.
If a particular packet identification has been added to the activity table, but is not subsequently sampled, the matching activity value will eventually decrease to zero. When the activity value decreases to zero, the monitor considers the record containing the associated identification to be empty and places a new sampled identification in the activity table. The result is that the activity table is constantly updated and contains an activity value for the most significant packet identifications handled by the switch.
In one embodiment the monitor is implemented in an application specific integrated circuit (ASIC) contained in a network switch. The ASIC contains RAM, in which the activity table and other volatile information such as the sampled packet""s identification is stored, and other circuits configured to perform the monitoring tasks in accordance with the present invention. The ASIC is connected to an external central processing unit, clock, and information busses.
The monitor ASIC is constructed using conventional techniques. In one embodiment the monitor circuits are specified using the VERILOG language and compiled using SYNOPSYS from a catalog of available circuits. The ASIC is then fabricated using conventional procedures and is installed in the switch for normal operation. In other embodiments a computer or other device is configured to implement the monitoring tasks in accordance with the invention. Computer readable media may be configured to store computer implemented instructions in accordance with the method of the present invention.